/*
 * Grafo.h
 *
 *  Created on: Jan 24, 2014
 *      Author: ik
 */

#ifndef GRAFO_H_
#define GRAFO_H_

#include <string>
#include <iostream>

#include <VertexSet.h>
#include <ValueArray.h>

using namespace std;

class DiGrafo
{

protected:
	// Una matriz simétrica de bits con las aristas existentes (verdaderas y falsas)
	int 		_n;
	VertexSet**	_arista;
	VertexSet*	_vertices;
	Lista*		_enumerablesI;
	VertexSet*	_working;

public:
	DiGrafo(int n);
	DiGrafo(DiGrafo &otro);
	DiGrafo(DiGrafo &otro, Lista& orden);
	DiGrafo(string archivoDIMACS);
	virtual ~DiGrafo();

	// Métodos exclusivos a los grafos direcionados

	/*!
	 * \brief Agrega un arco al digrafo.
	 *
	 * Si un de los extremos no es un vértice en el grafo, un error ocurre.
	 */
	void addArco(int i, int j);
	/*!
	 * \brief Borra una arista al grafo.
	 *
	 * Si un de los extremos no es un vértice en el grafo, un error ocurre.
	 */
	void delArco(int i, int j);
	/*!
	 * \brief Chequea si una pareja de vértices es un arco.
	 */
	bool isArco(int i, int j) const;
	void addVecinos(int i, const VertexSet& c);
	void delVecinos(int i, const VertexSet& c);

	// Métodos para grafo no direcionado subjacente

	/*!
	 * \brief Chequea si una pareja de vértices es una arista.
	 *
	 * Para un grafo no direcionado, si (i,j) está, entonces (j,i) está también
	 */
	virtual bool isArista(int i, int j) const;

	// Métodos comunes a los grafos y los digrafos

	/*
	 * \brief Convierte este grafo en incambiable.
	 *
	 * Una llamada ulterior a un método de modificación de este grafo genera un error.
	 *
	 * El método \c vecinos(i).size() calcula el grado de un vértice \c i de un grafo incambiable en tiempo constante.
	 */
	virtual void haceIncambiable();
	/*!
	 * \brief Agrega in vértice al grafo
	 *
	 * Los vértices no son creados con la creación del grafo. Se necesita agregarlos uno a
	 * uno.
	 */
	virtual void addVertice(int i);
	virtual void addAllVertices();
	virtual const VertexSet& vertices() const;
	/*!
	 * \brief Devuelve los vecinos de salida
	 */
	virtual const VertexSet& vecinos(int i) const;
	virtual bool isVertice(int i) const;
	virtual int getN() const;
	virtual void turnToComp();
	virtual void clear();
	virtual double getDensidad() const;
	bool containsAsSubgrafo(const DiGrafo& otro, const VertexSet& subgrafo);
	void copy(DiGrafo& otro);
	void copySubgrafo(const DiGrafo& otro, const VertexSet& subgrafo);

	template <typename T>
	const ValueArray<T> * grados() const;

	// Métodos para ordenar vértices
	virtual void crecienteGrado(Lista& orden);
	virtual void decrecienteGrado(Lista& orden);

	template <class T>
	void crecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const;

	template <class T>
	void decrecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const;

	struct ComparadorGradosCrecientes {
		DiGrafo const * _g;
		bool operator() (int a, int b) { return _g->vecinos(a).size() < _g->vecinos(b).size(); }
	} _compGradosCrecientes;

	struct ComparadorGradosDecrecientes {
		DiGrafo const * _g;
		bool operator() (int a, int b) { return _g->vecinos(a).size() > _g->vecinos(b).size(); }
	} _compGradosDecrecientes;

private:
	void initialize(int n);
};

class Grafo : public DiGrafo
{

public:
	Grafo(int n);
	Grafo(Grafo &otro);
	Grafo(Grafo &otro, Lista& orden);
	Grafo(string archivoDIMACS);
	virtual ~Grafo();

	// Métodos exclusivos a los grafos no direcionados

	/*!
	 * \brief Agrega una arista al grafo.
	 *
	 * Si un de los extremos no es un vértice en el grafo, un error ocurre.
	 */
	void addArista(int i, int j);
	/*!
	 * \brief Borra una arista al grafo.
	 *
	 * Si un de los extremos no es un vértice en el grafo, un error ocurre.
	 */
	void delArista(int i, int j);

	// Métodos modificados grafo no direcionado subjacente

	/*!
	 * \brief Chequea si una pareja de vértices es una arista.
	 */
	bool isArista(int i, int j) const;
	bool isClique(const VertexSet& c) const;
	bool isStable(const VertexSet& c) const;
	bool isInducedTree(const VertexSet& c) const;

	// Métodos comunes a los grafo y los digrafos

	void copy(Grafo& otro);
	void copySubgrafo(const Grafo& otro, const VertexSet& subgrafo);
	bool containsAsSubgrafo(const Grafo& otro, const VertexSet& subgrafo);

	template <typename T>
	const ValueArray<T> * grados() const;

	template <class T>
	void crecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const;

	template <class T>
	void decrecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const;
};

inline void DiGrafo::addVertice(int i)
{
	if (!isVertice(i))
	{
		_arista[i] = new VertexSet(_n);
		_vertices->add(i);
	}
}

inline void DiGrafo::addAllVertices()
{
	for (int i = 0; i < _n; i++)
		if (!isVertice(i))
			_arista[i] = new VertexSet(_n);
	_vertices->addAll();
}

inline void DiGrafo::addArco(int i, int j)
{
	_arista[i]->add(j);
}

inline void DiGrafo::delArco(int i, int j)
{
	_arista[i]->remove(j);
}

inline void Grafo::addArista(int i, int j)
{
	_arista[i]->add(j);
	_arista[j]->add(i);
}

inline void Grafo::delArista(int i, int j)
{
	_arista[i]->remove(j);
	_arista[j]->remove(i);
}

inline void DiGrafo::addVecinos(int i, const VertexSet& c)
{
	_arista[i]->addAll(c);
}

inline void DiGrafo::delVecinos(int i, const VertexSet& c)
{
	_arista[i]->removeAll(c);
}

inline bool DiGrafo::isVertice(int i) const
{
	return _vertices->contains(i);
}

inline bool DiGrafo::isArista(int i, int j) const
{
	return _arista[i]->contains(j) || _arista[j]->contains(i);
}

inline bool DiGrafo::isArco(int i, int j) const
{
	return _arista[i]->contains(j);
}

inline bool Grafo::isArista(int i, int j) const
{
	return _arista[i]->contains(j);
}

inline const VertexSet& DiGrafo::vertices() const
{
	return *_vertices;
}

inline const VertexSet& DiGrafo::vecinos(int i) const
{
	return *_arista[i];
}

template <typename T>
inline const ValueArray<T> * DiGrafo::grados() const
{
	class GradosArray : ValueArray<T> {
		friend class DiGrafo;
		const DiGrafo * _g;
		GradosArray(const DiGrafo * g) : ValueArray<T>(), _g(g) {
			ValueArray<T>::_indexOfMaxValue = 0;
			for (int i = 1; i < _g->getN(); i++)
				if ((*this)[ValueArray<T>::_indexOfMaxValue] < (*this)[i])
					ValueArray<T>::_indexOfMaxValue = i;
		};
		const T operator [](int i) const { return _g->vecinos(i).size(); };
	};
	return new GradosArray(this);
}

template <typename T>
inline const ValueArray<T> * Grafo::grados() const
{
	return DiGrafo::grados<T>();
}

/*!
 * \brief Devuelve la cantidad de vértices
 */
inline int DiGrafo::getN() const
{
	return _n;
}

/*!
 * \brief Devuelve la densidad
 *
 * No se lleva en cuenta los loops
 */
inline double DiGrafo::getDensidad() const
{
	int m = 0;
	int d = 0;
	for (VertexSetIterator it = _vertices->begin(); it != _vertices->end(); ++it)
	{
		m += vecinos(*it).size();
		if (isArista(*it,*it))
			d++;
	}
	return ((double) (m-d))/(_n*_n-_n);
}

template <class T>
inline void DiGrafo::decrecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const {
	struct ComparadorPesosGradosDecrecientes {
		DiGrafo const * _g;
		ValueArray<T> const * _pesos;
		bool operator() (int a, int b) { return (*_pesos)[a] > (*_pesos)[b] ? true : (*_pesos)[a] == (*_pesos)[b] ? _g->vecinos(a).size() > _g->vecinos(b).size() : false; }
	} _compPesosGradosDecrecientes;
	_compPesosGradosDecrecientes._g = this;
	_compPesosGradosDecrecientes._pesos = &pesos;
	sort(orden.begin(), orden.end(), _compPesosGradosDecrecientes);
}

template <class T>
inline void Grafo::decrecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const {
	DiGrafo::decrecientePesosGrado<T>(pesos, orden);
}

template <class T>
inline void DiGrafo::crecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const {
	struct ComparadorPesosGradosCrecientes {
		DiGrafo const * _g;
		ValueArray<T> const * _pesos;
		bool operator() (int a, int b) { return (*_pesos)[a] < (*_pesos)[b] ? true : (*_pesos)[a] == (*_pesos)[b] ? _g->vecinos(a).size() < _g->vecinos(b).size() : false; }
	} _compPesosGradosCrecientes;
	_compPesosGradosCrecientes._g = this;
	_compPesosGradosCrecientes._pesos = &pesos;
	sort(orden.begin(), orden.end(), _compPesosGradosCrecientes);
}

template <class T>
inline void Grafo::crecientePesosGrado(const ValueArray<T>& pesos, Lista& orden) const {
	DiGrafo::crecientePesosGrado<T>(pesos, orden);
}

inline void Grafo::copy(Grafo& otro)
{
	DiGrafo::copy(otro);
}

inline void Grafo::copySubgrafo(const Grafo& otro, const VertexSet& subgrafo)
{
	DiGrafo::copySubgrafo(otro, subgrafo);
}

inline bool Grafo::containsAsSubgrafo(const Grafo& otro, const VertexSet& subgrafo)
{
	DiGrafo::containsAsSubgrafo(otro, subgrafo);
}

#endif /* GRAFO_H_ */
